package main

import "fmt"

func maxSubArray(arr []int) int {
	size := len(arr)
	if size == 0 {
		return 0
	}
	dp := make([]int, size)
	dp[0] = arr[0]

	for i := 1; i < size; i++ {
		if dp[i-1] >= 0 {
			dp[i] = dp[i-1] + arr[i]
		} else {
			dp[i] = arr[i]
		}
	}

	max := dp[0]
	for i := 1; i < size; i++ {
		if dp[i] > max {
			max = dp[i]
		}
	}
	return max
}

func main() {
	//实验一文档中给出的几个例子
	arr1 := []int{1, -2, 3, 5, -1}
	arr2 := []int{1, -2, 3, -8, 5, 1}
	arr3 := []int{1, -2, 3,-2, 5, 1}
	result1 := maxSubArray(arr1)
	result2 := maxSubArray(arr2)
	result3 := maxSubArray(arr3)
	fmt.Println(result1)
	fmt.Println(result2)
	fmt.Println(result3)
}
